Reasoning About Natural Dynamics: Game Theory vs. Distributed Computing

Abstract:

Motivated by real-life environments such as Internet protocols and large-scale markets, we use ideas from game theory and distributed computing theory to study asynchronous dynamic environments where the prescribed behavior for each computational node (whether human or machine) is simple and natural (e.g., being "greedy" or minimizing "regret"). We investigate when the resulting dynamics are guaranteed to drive the system to a global equilibrium and explore the (computational and communication) complexity of checking for guaranteed convergence. We consider the surprising implications of our results across a wide variety of interesting and timely applications: today's protocols for routing and congestion control on the Internet, social networks, asynchronous circuits, and more.